#include <iostream>

using namespace std;

int comp(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}

class Find3Sum
{
private:
	int _sum;
	int* entireArray;
	int _size;

	void sortArray();
public:
	Find3Sum(int* arr, int size, int sum);
	void printSubsetsIndex();
};

Find3Sum::Find3Sum(int* arr, int size, int sum): _sum(sum), entireArray(arr), _size(size){};

void Find3Sum::sortArray()
{
	qsort(entireArray, _size, sizeof(int), comp);
}

void Find3Sum::printSubsetsIndex()
{
	sortArray();

	bool found = false;

	int i, m, n, _3sum;

	for (i = 0; i < _size; i++)
		cout <<entireArray[i] <<" ";
	cout <<endl;
	for (i = 0; i < _size; i++){
		m = i + 1;
		n = _size - 1;
		while (m < n){
			_3sum = entireArray[i] + entireArray[m] + entireArray[n];
			if ( _3sum == _sum){
				found = true;

				cout <<"found\n";
				cout <<i <<":" <<entireArray[i] <<" " <<m <<":" <<entireArray[m] <<" " <<n <<":" <<entireArray[n] <<" " <<endl;

			}

			/* has bugs here */
			if ( _3sum > _sum)
				n--;
			else
				m++;
		}
	}
/*
	if (found){
		cout <<"found\n";
	} else {
		cout <<"not found\n";
	}
	*/
}

int _3sum()
{
	int testData[] = {1, 2, 5, 5, 3, 3, 1};
	int sum = 10;

	Find3Sum finder(testData, sizeof(testData) / sizeof(int), sum);
	finder.printSubsetsIndex();

	cin.get();
	return 0;
}